МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра САПР
ДИНАМІЧНІ ОБ’ЄКТИ СКЛАДНОЇ СТРУКТУРИ. ТАБЛИЦІ, БІНАРНІ ДЕРЕВА
ЗВІТ
до лабораторної роботи № 14 з курсу:
“Алгоритмізація та програмування”
1. МЕТА РОБОТИ
Мета роботи – ознайомитись із особливостями побудови та застосування динамічних об’єктів складної структури: таблиць і бінарних дерев; з операція ми, які виконуються над елементами цих об’єктів. Набути практичних навичок програмування з використанням динамічних об’єктів складної структури зокрема бінарних дерева.
2. ЛАБОРАТОРНЕ ЗАВДАННЯ
Програма №1, Варіант №7
Відобразити за допомогою дерева оператор умови: IF <умова> THEN <оператор> ELSE <оператор>; Вивести на друк проміжний результат та результат після видалення гілки ELSE.
Блок-схема:
/
Код програми:
program if_tree;
uses crt;
type
tree = ^point;
point = record
key:string;
left:tree;
right:tree;
entry:string
end;
function find_tree(kl:string; var tr, rez:tree):boolean;
var p, q:tree;
b:boolean;
begin
b:=false;
p:=tr;
if tr<>nil then
repeat
q:=p;
if p^.key = kl then
b:= true
else
begin
q:=p;
if kl<p^.key then p:=p^.left
else p:=p^.right;
end
until b or (p=nil);
find_tree:=b;
rez:=q;
end;
procedure ins_tree(kl:string; var tr:tree; ent:string);
var
r, s:tree;
begin
if not find_tree(kl, tr, r) then
begin
new(s);
s^.key:=kl;
s^.entry:=ent;
s^.left:=nil;
s^.right:=nil;
if tr = nil then tr:=s
else
if kl<r^.key then
r^.left:=s
else
r^.right:=s
end
end;
procedure del_tree(var tr:tree; kl:string);
var q:tree;
procedure del(var r:tree);
begin
if r^.right = nil then
begin
q^.key:=r^.key;
q^.entry:=r^.entry;
q:=r;
r:=r^.left;
end
else del(r^.right);
end;
begin
if tr = nil then
writeln('Нема елемента з таким ключем')
else
if kl < tr^.key then
del_tree(tr^.left, kl)
else
if kl > tr^.key then
del_tree(tr^.right, kl)
else
begin
q:=tr;
if q^.right = nil then tr:=tr^.left
else
if q^.left = nil then tr:=tr^.right
else
del(q^.left);
end
end;
const k1 = 'if'; k2 = 'then'; k3 = 'else';
var
d:tree;
s1, s2, s3:string;
begin
d:=nil;
writeln('Введiть умову IF');
readln(s1);
writeln('Введiть оператор пiсля THEN');
readln(s2);
writeln('Введiть оператор пiсля ELSE');
readln(s3);
ins_tree(k1, d, s1);
ins_tree(k2, d, s2);
ins_tree(k3, d, s3);
writeln('Отримане дерево');
writeln(' ',d^.key);
writeln(' ',d^.entry);
writeln(' ', '/', ' ', '\');
writeln(' ', d^.left^.key, ' ', d^.right^.key);
writeln(' ', d^.left^.entry, ' ', d^.right^.entry);
del_tree(d, k3);
writeln('Нове дерево');
writeln(' ',d^.key);
writeln(' ',d^.entry);
writeln(' ', '\');
writeln(' ', d^.right^.key);
writeln(' ', d^.right^.entry);
end.
Результати обчислень:
/
3. ВИСНОВОК
В ході виконання цієї лабораторної роботи я ознайомився із особливостями побудови та застосування динамічних об’єктів складної структури: таблиць і бінарних дерев; з операція ми, які виконуються над елементами цих об’єктів, набув практичних навичок програмування з використанням динамічних об’єктів складної структури зокрема бінарних дерева.
